package pro11_20.pro14;

/**
 * @author yaohuaiying
 * @create 2018-02-09 14:13
 * 第14题（数组）：
题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

思路
    已经排好的数字    时间复杂为o(n)一层循环。。。。。  输入数k
    减法
    首尾相加>k 说明尾部太大 尾部向前
    首尾相加<k 说明前面太小 前面向前
    直到相等
 **/
public class Main {
    public static void main(String[] args) {
        int[] a = {1, 2, 4, 7, 11, 15, 19};
        int i = 0;
        int j = a.length - 1;
        int k = 20;
        if (k <= a[i] + a[j]) {
            while (i <= j) {
                int sum = a[i] + a[j];
                if (sum > k) {
                    j--;
                }
                if (sum < k) {
                    i++;
                }
                if (a[i] + a[j] == k) {
                    break;
                }
            }
            if (a[i] + a[j] == k) {
                System.out.println(a[i] + "+" + a[j] + "=" + k);
            } else {
                System.out.println("null");
            }
        }else {
            System.out.println("Null");
        }
    }


}
